package com.nanbei.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @ClassDescription: 基数排序
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/28 14:40
 */
public class RadixSort {

    public static void main(String[] args) {
        String[] strings = {"135", "158", "137", "138", "336", "567", "235", "456"};
        String[] strings1 = countSort(strings, 3);
        System.out.println(Arrays.toString(strings1));
    }

    /**
     * 基数排序
     * 按字符串的 最小位 --> 最大位  依次进行排序
     *
     * @param nums 字符数组
     * @param length 每个字符数组的长度
     * @return 排序后的字符数组
     */
    public static String[] countSort(String[] nums,int length) {
        ArrayList<ArrayList<String>> arrayLists = new ArrayList<>();

        // 创建10个桶，每个桶对应【0-9】10个数值
        for (int i = 0; i < 10; i++) {
            ArrayList<String> list = new ArrayList<>();
            arrayLists.add(list);
        }


        for (int i = length-1; i >= 0; i--) {
            // 将每个数值放入对应的桶中
            for (String num : nums) {
                int c = num.charAt(i)-48;
                ArrayList<String> list = arrayLists.get(c);
                list.add(num);
            }

            int index = 0;
            for (ArrayList<String> list : arrayLists) {
                for (String s : list) {
                    nums[index++] = s;
                }
                list.clear();
            }
            // 将每次按位数排序后的数组打印出来
            System.out.println(Arrays.toString(nums));
        }
        return nums;
    }
}
